#ifndef __POINT_IN_POLYGON_HPP__
#define __POINT_IN_POLYGON_HPP__

#include <vector>

class Point
{
public:
    Point(float x, float y) : x(x), y(y)
    {
    }
    bool isInRing(std::vector<Point> points, bool ignoreBoundary);

public:
    const float x;
    const float y;
};

bool Point::isInRing(std::vector<Point> points, bool ignoreBoundary)
{
    auto size = points.size();
    if (size < 3)
    {
        return false;
    }
    const auto first = points[0];
    const auto last = points[size - 1];
    if (first.x == last.x && first.y == last.y)
    {
        // repeated start-end point
        size--;
    }
    auto isInside = false;
    auto i = 0;
    auto j = size - 1;
    for (; i < size;)
    {
        auto xi = points[i].x;
        auto yi = points[i].y;
        auto xj = points[j].x;
        auto yj = points[j].y;
        auto onBoundary = (y * (xi - xj) + yi * (xj - x) + yj * (x - xi) == 0) &&
                          ((xi - x) * (xj - x) <= 0) && ((yi - y) * (yj - y) <= 0);
        if (onBoundary)
        {
            return !ignoreBoundary;
        }
        auto intersect = ((yi > y) != (yj > y)) &&
                         (x < (xj - xi) * (y - yi) / (yj - yi) + xi);
        if (intersect)
        {
            isInside = !isInside;
        }
        j = i;
        i++;
    }
    return isInside;
}

class LineString
{
public:
    LineString(const std::vector<Point> points) : points(points) {}

public:
    const std::vector<Point> points;
};

class Polygon
{
public:
    Polygon(const std::vector<LineString> lineStrings) : lineStrings(lineStrings)
    {
    }
    Polygon(const Polygon &polygon) : Polygon(polygon.lineStrings)
    {
    }
    Polygon() : Polygon(std::vector<LineString>()) {}
    bool containsPoint(Point point, bool ignoreBoundary) const;

public:
    const std::vector<LineString> lineStrings;
};

bool Polygon::containsPoint(Point point, bool ignoreBoundary) const
{
    if (lineStrings.size() <= 0)
    {
        return false;
    }
    const auto insidePoly = point.isInRing(lineStrings[0].points, ignoreBoundary);
    if (!insidePoly)
    {
        return false;
    }
    auto it = lineStrings.cbegin() + 1;
    for (; it < lineStrings.end(); it++)
    {
        const auto inHole = point.isInRing(it->points, !ignoreBoundary);
        if (inHole)
        {
            return false;
        }
    }
    return true;
}

class Options
{
};

#endif // __POINT_IN_POLYGON_HPP__
